package com.qxy.hot2;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : 戚欣扬
 * @description :随机链表复制
 */
public class Solution {
    public Node copyRandomList(Node head) {
        Node cur = new Node(-1);
        cur = head;
        if(cur==null)
        {return null;}
        //复制头结点初始化
        Node newHead =new  Node(0);
        Node cur2 = newHead;
        newHead.val = cur.val;
        Map<Node,Integer> nodeMap = new HashMap<>();
        Integer index = 0;
        while(cur.next!=null){
            //找到next val 创建节点 更新指针
            int val = cur.next.val;
            Node newNode = new Node(val);
            cur2.next = newNode;
            //保存cur节点及其位置
            nodeMap.put(cur,index);
            //更新指针下标
            cur = cur.next;
            cur2 = cur2.next;
            index++;
        }
        nodeMap.put(null,-1);
        //遍历head找到每一个节点random指针指向的index，将curNode的random指针指向index对应的节点
        Node curNode = newHead;
        while(head!=null){
            //找到random节点
            Integer curRandomIndex = nodeMap.get(head.random);
            if (curRandomIndex == -1) {
                curNode.random =null;
            }else{
                //将temp指针移动到index节点并更新curNode的random指针
                Node temp = newHead;
                while(curRandomIndex > 0){
                    temp = temp.next;
                }
                curNode.random = temp;
            }

            //更新指针
            curNode = curNode.next;
            head = head.next;
        }

        return newHead;
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

